#include<iostream>
using namespace std;

struct node
{
	int val;
	node *next;
	
	node(int val, node* next)
	{
		this->val = val;
		this->next = next;
	}
};

node* reversebytwo(node *head)
{
	if(head == NULL || head->next == NULL)
		return NULL;
	node *head_new = head->next;
	node *tail_new = NULL;
	node *odd = NULL; 
	node *even = NULL;
	bool is_odd = true;
	node *next = head;
	while(next)
	{
		if(is_odd)
		{
			odd = next;
			is_odd = false;
			next = next->next;
		}
		else
		{
			even = next;
			next = next->next;
			if(tail_new)
				tail_new->next = even;
			even->next = odd;
			tail_new = odd;
			is_odd = true;
		}
	}
	if(is_odd)
		tail_new ->next = NULL;
	else
		tail_new ->next = odd; 
	return head_new;
}

node* reversebytwo_r(node *head)
{
	if(head == NULL || head->next == NULL)
		return head;
	node *second = head->next;
	head->next = reversebytwo_r(second->next);
	second->next = head;
	return second;
}

void print(node *head)
{
	while(head)
	{
		cout << head->val << " ";
		head = head->next;
	}
	cout << endl;
}

int main()
{
	node node4(4, NULL);
	node node3(3, &node4);
	node node2(2, &node3);
	node node1(1, &node2);

	print(&node1);
	node *new_head = reversebytwo_r(&node1);	
	print(new_head);

	node node33(33, NULL);
	node node22(22, &node33);
	node node11(11, &node22);
	print(&node11);
	new_head = reversebytwo_r(&node11);
	print(new_head);
	return 0;
}
